//
// Created by fh on 2021/7/16.
//

#include "RecallArithmetic.h"

static a = 0;
static b = 0;

/* 检查行列 */
int checkRowColumn(int row,int column,int result[]) {
    b++;
    int t = 1;
    for (int i = row-1; i >= 0; --i) {
        int left = column - t;
        int right = column + t;
        t++;
        if (result[i] == column) {
            // 列已经有了
            return 0;
        }
        if (left >= 0) {
            if (result[i] == left) {
                return 0;
            }
        }
        if (right < 8) {
            if (result[i] == right) {
                return 0;
            }
        }
    }
    return 1;
}

/* 八皇后问题 */
void eightQueen(int row,int result[]) {
    if (row == 8) {
        a++;
        printf("a: %d\n",a);
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (result[i] == j) {
                    printf("Q ");
                } else {
                    printf("* ");
                }
            }
            printf("\n");
        }
        printf("\n");
        return;
    }
    // 每一行都有八种放法
    for (int column = 0; column < 8; ++column) {
        if (checkRowColumn(row,column,result) == 1) {
            result[row] = column;
            eightQueen(row+1,result);
        }
    }

}

void ff(int i,int n) {
    printf("i: %d\n",i);
    if (i == n) {
        return;
    }
    ff(i+1,n);
    printf("返回时i:%d\n",i);
}

static int maxW = -1; // 结果放到maxW中
static int weight[] = {2,2,4,6,3}; // 物品重量
static int m = 5; // 物品个数
static int w = 9; // 背包承受的最大重量

void f(int i,int cw) {
    printf("----- i:%d ----- cw:%d\n",i,cw);
    if (cw == w || i == m) {
        if (cw > maxW) {
            maxW = cw;
        }
        return;
    }
    f(i+1,cw);
    if (cw + weight[i] <= w) {
        f(i+1,cw + weight[i]);
    }
}

static tm = 0;
void test(int row) {
    tm++;
    printf("------------------ row: %d\n",row);
    if (row == 2) {
        return;
    }
    for (int i = 0; i < 4; ++i) {
//        printf("i:%d\n",i);
        test(row+1);
    }
}


/* 测试demo */
void recallArithmeticTestDemo() {


    {
        f(0,0);
        printf("maxW: %d\n",maxW);
    }
    return;
    {
        ff(1,6);
    }
    return;
    {
        printf("----------------- 八皇后问题 --------------\n");
        int result[8];
        eightQueen(0,result);
        printf("----------------- 实际参数 --------------\n");
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (result[i] == j) {
                    printf("Q ");
                } else {
                    printf("* ");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    printf("b:%d\n",b);

    {
        test(0);
        printf("%d\n",tm);
    }
    return;

}

